package top.minuy.structure.graph.cycle.dfs;

import top.minuy.structure.graph.representations.table.Graph;

/**
 * 环检测，深度优先遍历
 *
 * @author Minuy
 * @time 21:52
 * @date 2021/11/18
 */
public class CycleDetection {

    private Graph g;
    private boolean[] isVisited;

    private boolean hasCycle;

    public CycleDetection(Graph g) {
        this.g = g;

        if (g.isDirected()){
            throw new IllegalArgumentException("CycleDetection only works in undirected graph.");
        }

        // 开辟空间，初始化内容
        this.isVisited = new boolean[g.V()];

        // 从源结点开始对整个联通分量进行遍历
        // （因为求路径，不同联通分量之间肯定没有路径）
        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                if (dfs(v, v)) {
                    hasCycle = true;
                    return;
                }
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param v      遍历开始的顶点
     * @param parent v的上一个被遍历的顶点
     * @author Minuy
     * @date 2021/11/16 23:42
     */
    private boolean dfs(int v, int parent) {
        // 如果已经被遍历了，并且不是上一个节点
        isVisited[v] = true;

        for (Integer w : g.adj(v)) {
            // v 本顶点， parent 父顶点， w 下一个顶点
            if (!isVisited[w]) {
                if (dfs(w, v)) {
                    return true;
                }
            } else if (parent != w) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查询这个图中有没有环
     *
     * @return boolean 有无环
     * @author Minuy
     * @date 2021/11/18 22:00
     */
    public boolean hasCycle() {
        return hasCycle;
    }

    @Override
    public String toString() {
        return String.valueOf(hasCycle());
    }
}
